package com.wzq.solution;

import java.util.HashMap;
import java.util.Map;

class Solution62 {

    Map<String,Integer> map = new HashMap<String,Integer>();
    public int uniquePaths(int m, int n) {

        if(m==0 && n==0){
            return 1;
        }


        int cnt = 0;
        int v = 0;
        if(m!=0 ){
            String k = (m-1)+"_"+n;
            if(map.containsKey(k)){
                v =map.get(k);
            }else{
                v = uniquePaths(m-1,n);
                map.put(k,v);
            }
            cnt += v;
        }

        if(n!=0 ){

            String k = m+"_"+(n-1);

            if(map.containsKey(k)){
                v =map.get(k);
            }else{
                v = uniquePaths(m,n-1);
                map.put(k,v);
            }

            cnt += v;
        }

        return cnt;

    }


    public static void main(String[] args) {
        new Solution62().uniquePaths(3,2);
    }
}